package interview;

import basic.sort.utils.NodeUtil;

import javax.swing.tree.TreeNode;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description interview
 * @since JDK1.8
 *
 * 检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。
 *
 * 如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，
 * 也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/check-subtree-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class CheckSubTree {
    public static boolean checkSubTree(NodeUtil t1, NodeUtil t2) {

        if (t1 == null && t2 == null) {
            return true;
        }
        if (t1 == null || t2 == null) {
            return false;
        }

        return helper(t1, t2) || checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2);
    }

    public static boolean helper(NodeUtil t1, NodeUtil t2) {

        if (t1 == null && t2 == null) {
            return true;
        }
        if (t1 == null || t2 == null) {
            return false;
        }

        return t1.value == t2.value && helper(t1.left, t2.left) && helper(t1.right, t2.right);
    }

    public static void main(String[] args) {
        NodeUtil t1 = new NodeUtil(1);
        t1.right = new NodeUtil(2);
        t1.right.left = new NodeUtil(4);
        NodeUtil t2 = new NodeUtil(2);
        t2.left = new NodeUtil(4);

        System.out.println(checkSubTree(t1, t2));
    }
}
